package com.lx.algorithm.Tree;

import java.io.Serializable;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-11-08 13:12:16
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-11-08     张李鑫                     1.0         1.0 Version
 */
public class LevelTraversalBT {

    /**
     * 二叉树的按层遍历
     *
     * 1）其实就是宽度优先遍历，用队列
     *
     * 2）可以通过设置flag变量的方式，来发现某一层的结束（看题目）
     */


    public static void printLevelByQueue(Node tree){
        if (tree==null){
            return;
        }
        //队列先进先出 有节点就往里加
        Queue<Node> list = new LinkedList<>();
        list.add(tree);
        while (!list.isEmpty()){
            Node poll = list.poll();
            System.out.println(poll.value);
            if (poll.left!=null){
                list.add(poll.left);
            }
            if (poll.right!=null){
                list.add(poll.right);
            }
        }
    }

    public static void main(String[] args) {
        Node<Integer> node = new Node<>(98);
        Node<Integer> node1 = new Node<>(70);
        Node<Integer> node3 = new Node<>(72);
        Node<Integer> node4 = new Node<>(69);
        Node<Integer> node5 = new Node<>(52);
        Node<Integer> node6 = new Node<>(68);
        Node<Integer> node7 = new Node<>(93);
        Node<Integer> node8 = new Node<>(87);
        Node<Integer> node9 = new Node<>(71);
        Node<Integer> node10 = new Node<>(3);
        node.left = node1;
        node1.left = node3;
        node3.left = node4;
        node1.right = node5;
        node5.right = node6;
        node.right = node7;
        node7.left = node8;
        node8.left = node9;
        node8.right = node10;
        printLevelByQueue(node);
    }
}
